#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();
        if(n *m == 0) return n+m;
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i = 0; i <= n; ++i) {
            dp[0][i] = i;
        }
        for(int j = 0; j <= m; ++j) {
            dp[j][0] = j;
        }
        int left, down, left_down;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                left = dp[i-1][j]+1;
                down = dp[i][j-1]+1;
                left_down = dp[i-1][j-1];
                if(word1[i] != word2[j]) left_down += 1;
                dp[i][j] = min(left, min(down, left_down));
            }
        }
        return dp[n][m];
    }
};